package com.datastructures2.search;


/**
 * @author MaoLin Wang
 * @date 2020/2/1311:43
 */
public class BinarySearchTree<T extends Comparable<? super T>>  {

    private TreeNode<T> root;

    public BinarySearchTree(TreeNode<T> root) {
        this.root = root;
    }

    public int height(TreeNode<T> root){
        if (root==null){
            return -1;
        }
        return 1+Math.max(height(root.lchild),height(root.rchild));
    }
    public void preOrder(TreeNode<T> root){
        if (root!=null){
            System.out.println(root.data);
            preOrder(root.lchild);
            preOrder(root.rchild);
        }
    }
    public void midOrder(TreeNode<T> root){
        if (root!=null){
            midOrder(root.lchild);
            System.out.println(root.data);
            midOrder(root.rchild);
        }
    }
    public void lastOrder(TreeNode<T> root){
        if (root!=null){
            lastOrder(root.lchild);
            lastOrder(root.rchild);
            System.out.println(root.data);
        }
    }
    public void makeEmpty(){
        root=null;
    }
    public boolean isEmpty(){
        return this.root==null;
    }
    public boolean contains(T x){
        return  contains(x,root);
    }
    private boolean contains(T x, TreeNode<T> root) {
         if (root==null){
             return false;
         }
         int result=x.compareTo(root.data);
         if (result<0){
             return contains(x,root.rchild);
         }else if (result>0){
             return contains(x,root.lchild);
         }else {
             return true;
         }

    }

    private TreeNode<T> findMin(TreeNode<T> root){
       if (root==null){
           return null;
       }
       while (root.lchild!=null){
           root=root.lchild;
       }
       return root;
    }

    public TreeNode<T> findMax(TreeNode<T> root){
        if (root==null){
            return null;
        }
        while (root.rchild!=null){
            root=root.rchild;
        }
        return root;
    }

    public void insert(T x){
        if (x==null){
            throw new IllegalArgumentException("参数为空");
        }
         insert(x,root);
    }
    private TreeNode<T> insert(T x,TreeNode<T> root){
      if (root==null){
          return new TreeNode<>(x);
      }String username="wangmaolin";
      String password="1234556";
      int result=x.compareTo(root.data);
      if (result<0){
          root.lchild=insert(x,root.lchild);
      }else if (result>0){
          root.rchild=insert(x,root.rchild);
      }
      return root;

    }
    public void remove(T x){
        if (x==null){
            return;
        }
        remove(x,root);
    }

    /**
     * 删除一个节点
     * 1.如果是叶子节点，则直接删除
     * 2.如果有一个孩子，让当前节点等于那个孩子
     * 3.如果有两个孩子，让当前节点的值等于右孩子中最小的一个节点的值，然后再同样的方法删除右孩子最小值的节点
     * @param x
     * @param root
     * @return
     */
    private TreeNode<T> remove(T x,TreeNode<T>root){
       if (root==null){
           return null;
       }
       int result=x.compareTo(root.data);
       if (result<0){
           root.lchild=remove(x,root.lchild);
       }else if (result>0){
           root.rchild=remove(x,root.rchild);
       }else if (root.lchild!=null && root.rchild!=null){
           root.data=findMax(root).data;
           root.rchild=remove(root.data,root.rchild);
       }else {
           root=root.lchild==null?root.rchild:root.lchild;
       }
       return root;
    }
    public static void main(String[] args) {
        TreeNode<Integer> root = new TreeNode<>(5);
        BinarySearchTree<Integer> tree = new BinarySearchTree<>(root);
        tree.insert(1);
        tree.insert(2);
        tree.insert(3);
        tree.insert(7);
        tree.insert(9);
        tree.insert(10);
        tree.insert(0);
        tree.remove(0);
        System.out.println(tree.contains(3));
        System.out.println(tree.findMin(root));

    }
}

class TreeNode<T>{
    T data;
    TreeNode lchild;
    TreeNode rchild;

    public TreeNode(T data) {
        this(data,null,null);
    }

    public TreeNode(T data, TreeNode lchild, TreeNode rchild) {
        this.data = data;
        this.lchild = lchild;
        this.rchild = rchild;
        int []a={1};
    }

    @Override
    public String toString() {
        return "TreeNode{" +
                "data=" + data +
                ", lchild=" + lchild +
                ", rchild=" + rchild +
                '}';
    }

}
